#include<stdio.h>
int inf=9999999;
int e[1005][1005];
int main()
{
 
    int n,m,r,a,b,c,k,i,j,sum=0;
    while(scanf("%d%d%d",&n,&m,&r)!=EOF)
    {
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(i==j)    e[i][j]=0;
            else        e[i][j]=inf;
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        e[a][b]=c;
    }
    for(k=0;k<n;k++)
        for(i=0;i<n;i++)
            if(e[r][k]<inf&&e[k][i]<inf&&e[r][i]>e[r][k]+e[k][i])
                    e[r][i]=e[r][k]+e[k][i];
    for(i=0;i<n;i++)
    {
        if(e[r][i]!=inf&&e[r][i]<=0)
        {
            sum++;
        }
    }
    if(sum<n)
    {
    for(i=0;i<n;i++)
    {
        if(e[r][i]!=inf )
            printf("%d\n",e[r][i]);
        else
            printf("INF\n");
    }
    }
    else
    {
        printf("NEGATIVE CYCLE\n");
    }
    }
    return 0;
}